Redessiner un graphe sans que les arêtes se coupent - Corrigé

Énoncé

Dans cet exercice, on s'intéresse au graphe suivant.

1. Est-il simple ? 

2. Est-il complet ?

3. Proposer un autre dessin pour ce graphe où les arêtes ne se coupent pas.

Solution

1. Ce graphe est simple, il n'y a ni boucles ni arêtes parallèles.

2. Ce graphe n'est pas complet. Par exemple, les sommets 3 et 4 ne sont pas reliés par une arête.

3. On peut le dessiner ainsi :